--
-- FIBONACCI.LUA            Copyright (c) 2007, Asko Kauppi <akauppi@gmail.com>
--
-- Parallel calculation of Fibonacci numbers
-- 
-- References:
--      Intel Threading Building Blocks, 'test all'
--      <http://shareit.intel.com/WikiHome/Articles/111111316>
--
-- To do:
--      - ...
--

require "lanes"
require "assert"    -- assert.fails()


-- Threshold for serial calculation (optimal depends on multithreading fixed
-- cost and is system specific)
--
--local THRESHOLD= 10


-- Fibonacci numbers by Lucas formula
--
-- uint= fib( n_uint )
--
local function fib( n )
    --
    local sum
    local floor= assert(math.floor)

    io.stderr:write( "fib("..n..")\n" )

    if n <= 2 then    
        sum= n==0 and 0 or 1;   -- 0,1,1, ...
--[[
    else if n <= THRESHOLD then
        ..
]]
    else
        -- Splits into two; this task waits for combining the results
        --
        local a= self( floor(n/2) +1 )
        local b= self( floor(n/2) -1 + n%2 )

        -- children run

        local a2= a[0]^2
        local b2= b[0]^2
        
        sum = (n%2==1) and a2+b2 or a2-b2
    end

    io.stderr:write( "fib("..n..") = "..sum.."\n" )
    
    return sum
end

--
local n= 123456789
local launcher= lanes.prepare"io,math" ( fib )

launcher(n)

io.stderr:print( "\nFibonacci number #"..n.." is "..x.."\n" )
